/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-05-26 13:04:21
 * @LastEditors: lily
 * @LastEditTime: 2021-05-26 14:09:13
 */
/*
 * @lc app=leetcode.cn id=303 lang=javascript
 *
 * [303] 区域和检索 - 数组不可变
 */

// @lc code=start

//  思想：前缀和
//  sum(i,j) = preSum[j] - preSum[i] + nums[i]
//           = preSum[j] - preSum[i - 1]
//  使preSum[0] = 0 使得式子成立

//  复杂度：O(n) O(n) 每次查询O(1)


/**
 * @param {number[]} nums
 */
var NumArray = function (nums) {
    this.preSum = new Array(nums.length + 1).fill(0)
    for (let i = 1; i < nums.length + 1; i++) {
        this.preSum[i] = this.preSum[i - 1] + nums[i - 1]
    }
};

/** 
 * @param {number} left 
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
    return this.preSum[right + 1] - this.preSum[left]
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(left,right)
 */
// @lc code=end
nums = [-2, 0, 3, -5, 2, -1]
var obj = new NumArray(nums)